package danran.bfs;


import java.util.*;
import java.util.stream.Collectors;

/**
 * @Classname CloneGraph
 * @Description TODO
 * @Date 2021/8/27 12:11
 * @Created by ASUS
 */
public class CloneGraph {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Queue<Node> q = new ArrayDeque<>();
        Map<Integer, Node> map = new HashMap<>();
        q.offer(node);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node cur = q.poll();
                assert cur != null;
                List<Node> neighbors = cur.neighbors;
                if (map.containsKey(cur.val)) {
                    Node n = map.get(cur.val);
                    for (Node neighbor : neighbors) {
                        if (!contains(n.neighbors, neighbor)) {
                            if (!map.containsKey(neighbor.val)) {
                                Node newNei = new Node(cur.val);
                                map.put(cur.val, newNei);
                                n.neighbors.add(newNei);
                            } else {
                                n.neighbors.add(map.get(neighbor.val));
                            }
                        }
                    }
                    continue;
                }
                Node newNode = new Node(cur.val);

                for (Node neighbor : neighbors) {
                    q.offer(neighbor);
                    Node newNeighbor = new Node(neighbor.val);
                    map.put(newNeighbor.val, newNeighbor);
                    newNode.neighbors.add(newNeighbor);
                }
                map.put(newNode.val, newNode);
            }
        }
        return map.get(node.val);
    }

    public boolean contains(List<Node> a, Node node) {
        List<Integer> collect = a.stream().map(n -> n.val).collect(Collectors.toList());
        return collect.contains(node.val);
    }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
